\section{树算法}
\subsection{二叉树层序遍历}
\begin{example}
给你一个二叉树，请你返回其按层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。示例：二叉树：[3,9,20,null,null,15,7],
\end{example}
\begin{Textcode}
3
/ \
9  20
/    \
15     7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
\end{Textcode}
\begin{Mind}{二叉树层序遍历}{}
使用queue进行BFS，不同于打印无差别打印BFS中所有元素，这里要求按层将结果存储起来。也是这个问题的难点之一，这里的做法是队列中的元素是当前层的节点个数，存储数据到结果中的时候只需要遍历queue.size即可。实现如\coderef{code:bfsNotRec}
\end{Mind}
\begin{longlisting}
\caption{BFS(队列实现层序遍历)}
\cppfile[firstline=6,lastline=26]{third_party/coding/cxx/algorithm/datastruct/src/levelOrder.cc}
\label{code:bfsNotRec}
\end{longlisting}
递归实现\coderef{code:travelWithLevel}。
\begin{longlisting}
\caption{层序遍历}
\cppfile[firstline=28,lastline=42]{third_party/coding/cxx/algorithm/datastruct/src/levelOrder.cc}
\label{code:travelWithLevel}
\end{longlisting}
\subsection{判断子树在不在另一棵树上面}
\emph{约定空树不是任意一个树的子结构}
\begin{example}[判断树是否包含另一棵子树]
说明：
\begin{itemize}
	\item 子树为空，根据约定判断返回false。
	\item 树为空，空树不包含任何子树，返回false。
	\item 如果树和子树都不为空，根据根节点判断子树是否相同。
	      \begin{itemize}
		      \item 子树相同：返回true。
		      \item 子树不同:则说明和子树相同的节点可能并非当前根节点，选择其左右节点分别递归调用，两者有一个为true则结果为true。
	      \end{itemize}
\end{itemize}
\end{example}
\begin{figure}
	\centering
	\includegraphics[width=.6\textwidth]{isSubStructure}
	\caption{判断子树是不是树的一部分}
	\label{fig:isSubStructure}
\end{figure}
算法实现\coderef{code:inAnotherTree}。
\begin{longlisting}
	\caption{判断树是否被包含}
	\cppfile[firstline=43,lastline=58]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:inAnotherTree}
\end{longlisting}
\subsection{树的镜像}
\begin{Mind}{树的镜像}{}
对于根节点的左孩子保存起来，左孩子指向右孩子的mirror（如果直接指向右孩子会出现右孩子的子节点没有镜像）。这时候将右节点指向保存的左孩子mirror，最后返回根节点。算法实现\coderef{code:mirrorTree}。
\end{Mind}
树的镜像\figref{fig:mirrirTree}。
\begin{figure}
	\centering
	\includegraphics[width=.6\textwidth]{mirror_tree}
	\caption{树的镜像}
	\label{fig:mirrirTree}
\end{figure}
\begin{longlisting}
	\caption{树的镜像}
	\cppfile[firstline=60,lastline=69]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:mirrorTree}
\end{longlisting}
\begin{Mind}{树的镜像深搜}{}
深度优先搜索实现：深度优先搜索每个节点，对每个节点的左右子节点交换。最后返回根节点，实现如\figref{code:mirrorTreeWithDFS}。
\end{Mind}
\begin{longlisting}
	\caption{树的镜像（深搜）}
	\cppfile[firstline=72,lastline=91]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:mirrorTreeWithDFS}
\end{longlisting}
% \subsection{二叉树展开为链表}
% 如\figref{fig:flatten} 给你二叉树的根结点 root ，请你将它展开为一个单链表：
% \begin{itemize}
% 	\item 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
% 	\item 展开后的单链表应该与二叉树 先序遍历 顺序相同。
% \end{itemize}
% \begin{figure}[!htbp]
% 	\centering
% 	\includegraphics[width=0.5\textwidth]{flatten}
% 	\caption{二叉树转换为链表}
% 	\label{fig:flatten}
% \end{figure}

\subsection{二叉树的最大宽度}
给你一棵二叉树的根节点 root ，返回树的最大宽度 。树的最大宽度是所有层中最大的宽度 。每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
\begin{Mind}{二叉树的最大宽度}{}
	BFS遍历树，对树中的节点记录下索引，最大索引是当前层最右侧的节点和最左侧节点的索引差+1。
\end{Mind}
\begin{figure}
	\centering
	\includegraphics[width=0.5\textwidth]{widthOfBinaryTree}
	\caption{二叉树的最大宽度}
	\label{fig:widthOfBinaryTree}
\end{figure}

\begin{longlisting}
	\caption{二叉树的最大宽度}
	\cppfile[firstline=453,lastline=484]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:widthOfBinaryTree}
\end{longlisting}
\subsection{合并二叉树}
\begin{example}[合并二叉树]
	想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。返回合并后的二叉树。合并示意图如\figref{fig:mergeTrees}。
\end{example}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.6\textwidth]{mergeTrees}
	\caption{合并二叉树示意图}
	\label{fig:mergeTrees}
\end{figure}
\begin{itemize}
	\item 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
	\item 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
	\item 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。
\end{itemize}
实现\coderef{code:mergeTree}。
\begin{longlisting}
	\caption{合并二叉树}
	\cppfile[firstline=229,lastline=242]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:mergeTree}
\end{longlisting}
\subsection{判断二叉树是不是对称二叉树}
\begin{example}[判断二叉树是是对称二叉树]
	\begin{figure}[H]
		\centering
		\includegraphics[width=0.6\textwidth]{sym_tree}
		\caption{对称二叉树}
		\label{fig:sym_tree}
	\end{figure}
\end{example}
\begin{Mind}{判断对称二叉树}{}
	假设两棵完全相同的树分别遍历两棵树，中序遍历（根左右），先对比根节点，如果根节点不为空且值相同，我们递归对比a树的左节点和B树的右节点与b树的左节点于a树的右节点。
\end{Mind}
\begin{longlisting}
	\caption{是否为对称二叉树}
	\cppfile[firstline=3,lastline=25]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:isSymTree}
\end{longlisting}
\subsection{判断二叉搜索树}
\begin{example}
	\figref{fig:isValidBST}判断一棵树是否为二叉搜索树（BST，\textbf{左节点均比根节点小，右节点均比根节点大）}。
\end{example}
\vspace{10pt}
\begin{figure}
	\centering
	\includegraphics[width=.4\textwidth]{isValidBST}
	\caption{二叉搜索树}
	\label{fig:isValidBST}
\end{figure}
\begin{Mind}{判断二叉搜索树思路}{}
	如果树的根节点为空，则树是二叉搜索树（这个是根据递归条件判断的）。否则需要根据二叉搜索树规则判断。递归调用的时候传入最小值和最大值，分别用根节点的值和其比较，不满足则不为二叉搜索树，否则左子节点应该小于根节点，同时右子节点应该大于根节点。为了能让根节点和左右节点比较数值，最开始的情况应该是一定满足然后就可以拿到根节点的值，递归比较左右子节点的时候将这个值给他们进行比较。
\end{Mind}
\begin{longlisting}
	\caption{是否为二叉搜索树}
	\cppfile[firstline=93,lastline=106]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:isBSt}
\end{longlisting}
\subsection{分层打印每一层的元素}
\begin{example}
   分层打印每一行的元素的时候需要记录下当前层节点的数量，打印完节点后输出换行。
\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{bfs_layer}
\caption{分层打印}
\end{figure}
\end{example}
\begin{longlisting}
	\caption{分层打印}
	\cudafile[firstline=6,lastline=26]{third_party/coding/cxx/algorithm/datastruct/src/levelOrder.cc}
	\label{code:bfs_layer}
\end{longlisting}
\subsection{二叉树的右视图}
\begin{example}[二叉树的右视图]
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。示例 1：

输入：root = [1,2,3,4,null,null,null,5]

输出：[1,3,4,5]示意图如\figref{fig:rightSideView}
\end{example}

\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{rightSideView}
	\caption{二叉树的右视图}
	\label{fig:rightSideView}
\end{figure}
\begin{Mind}{二叉树的右视图}{}
	BFS记录每层的最后一个元素，其就是右视图的元素。这里实现的时候因为每一层只有最后的一个元素需要加入结果，所以层id直接可以作为结果数组的索引。添加元素的时候的逻辑是：这一层的元素没有加入则直接将元素加入结果列表否则将层的后一个元素替换当前元素以此来保证每一层只有一个元素。
\end{Mind}
\coderef{code:rightSideView} 代码实现中先加入左节点然后才是右节点，这样出队列的元素中当前层最后一个元素就是当前层的最后一个元素。如果先加入右节点然后加入左节点每一层出队列的第一个元素为最后一个元素。
\begin{longlisting}
	\caption{二叉树的右视图}
	\cudafile[firstline=632,lastline=660]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:rightSideView}
\end{longlisting}

\subsection{二叉树的深度}
\begin{example}[二叉树最大深度]
	如\figref{fig:treeMAxDepth}，如果节点是根节点，深度为1,如果节点只有子树，深度为左子树节点+1，如果是只有右子树，深度是右子树+1,如果两者都有，深度为左右子树深度的最大值。
\end{example}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{tree_depth}
	\caption{树的深度}
	\label{fig:treeMAxDepth}
\end{figure}
代码实现\coderef{code:maxDeepOfTree}。
\begin{longlisting}
	\caption{树的深度}
	\cppfile[firstline=144,lastline=154]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:maxDeepOfTree}
\end{longlisting}

\subsection{二叉树的最小深度}
\begin{example}[二叉树最小深度]
	如\figref{fig:treeMinDepth}最小深度是根节点到最近叶子节点的最短路径上的节点数量，单链表的最小深度不为1而是链表的长度。
\end{example}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{minDepth}
	\caption{树的最小深度}
	\label{fig:treeMinDepth}
\end{figure}
实现如\coderef{code:minDepthOfTree}
\begin{longlisting}
	\caption{树的最小深度}
	\cppfile[firstline=108,lastline=118]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:minDepthOfTree}
\end{longlisting}

\begin{itemize}
	\item 时间复杂度：$O(N)$（必须访问所有的节点才能知道最小深度）。
	\item 空间复杂度：$O(H)$，$H$为树的高度（必须存储最长路径），链表的时候最长路径为O(N)，一般时刻为$logN$。
\end{itemize}
% \subsection{树的最小高度}
% \begin{example}{}
% 给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。示例：
% 给定有序数组: [-10,-3,0,5,9],

% 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

%           0 
%          / \ 
%        -3   9 
%        /   / 
%      -10  5
% \end{example}
% \begin{Mind}{树的最小高度}

% \end{Mind}
% \begin{longlisting}
% 	\caption{树的最小高度}
% 	\cppfile[firstline=114,lastline=136]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
% 	\label{code:highOfTree}
% \end{longlisting}
% \begin{itemize}
% 	\item 时间复杂度：O(N)（最差情况还是需要访问到最后一个节点才知道最小深度）。
% 	\item 空间复杂度：O(N)（存储所有的节点）。
% \end{itemize}
\subsection{二叉树的所有路径}
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。例\figref{fig:binaryTreePaths}。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.3\textwidth]{binaryTreePaths}
	\caption{二叉树的所有路径}
	\label{fig:binaryTreePaths}
\end{figure}
DFS实现，发现叶子节点后将结果写入。
\begin{longlisting}
	\caption{二叉树的所有路径（递归实现）}
	\cppfile[firstline=244,lastline=263]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:binaryTreePathsRec}
\end{longlisting}
上述\coderef{code:binaryTreePathsRec}实现中对于路径的保存。迭代实现需要用栈模拟递归调用过程中path的退栈。实现如\coderef{code:binaryTreePathsIter}
\begin{longlisting}
	\caption{二叉树的所有路径（迭代实现）}
	\cppfile[firstline=272,lastline=306]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:binaryTreePathsIter}
\end{longlisting}
\subsection{根节点到子节点最短距离}
\begin{example}[美团2018笔试]
	给定输入节点n，节点之间的关系，求从根节点到各个子节点的最短路径。例如：
	\begin{figure}[H]
		\centering
		\includegraphics[width=0.5\textwidth]{shortestDis}
		\caption{最短距离}
		\label{fig:meituan_1}
	\end{figure}
	\figref{fig:meituan_1} 输出最大短路径为1-2-1-3-4-3-5-6,最短路径长度为7.
\end{example}
\begin{Mind}{树的最小深度}{}
	最短路径长度为边的数目减去最大边长，即短路径走重复，长路径不走重复，最短路径为总边的2倍减去最大路径（$2*(Node-1)-maxpath$）。代码实现用一个传入参数记录当前访问到for循环结束后的边数，防止了递归调用中该变量被初始化。改变其值。
\end{Mind}
TODO: 重构树的最小深度
%\begin{longlisting}
%	\caption{树的最小深度}
%	\cppfile[firstline=1,lastline=42]{code/offer/meituan/main.cpp}
%	\label{code:minDepthOfTree}
%\end{longlisting}
\subsection{求根节点到叶节点数字之和}
根节点到叶子节点的数字和。
\begin{Textcode}
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字，例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。计算从根节点到叶节点生成的 所有数字之和 。叶节点 是指没有子节点的节点。
\end{Textcode}
\begin{Mind}{栈实现思路}{}
	每一个节点保存当前的值和到达当前节点的数字。\figref{fig:sumNumbers}中对于节点9，如果到达节点意味着至少能得到49。如果走到了下一个节点5，此时至少是490，然后结果是495。此时没有子节点则结束。计算下一个节点需要上一个节点的值，所以栈中数据包含了到达当前节点的值。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=\textwidth]{sumNumbers}
	\caption{求根节点到叶节点数字之和}
	\label{fig:sumNumbers}
\end{figure}

\begin{longlisting}
	\caption{求根节点到叶节点数字之和（栈实现）}
	\cppfile[firstline=321,lastline=347]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:sumNumbers}
\end{longlisting}
需要注意的是第一个节点我们初始化pre\_value=0。递归实现如\coderef{code:sumNumbersRec}
\begin{longlisting}
	\caption{求根节点到叶节点数字之和（递归实现）}
	\cppfile[firstline=348,lastline=385]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:sumNumbersRec}
\end{longlisting}

\subsection{将有序数组转化为二叉树}
\begin{example}[将有序数组转化为二叉树]
	将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:
	给定有序数组: [-10,-3,0,5,9],一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示\figref{fig:balanceBST}这个高度平衡二叉搜索树：
\end{example}
\begin{figure}
	\centering
	\includegraphics[width=0.5\textwidth]{balenceBST}
	\caption{平衡二叉树示意图}
	\label{fig:balanceBST}
\end{figure}
\begin{Mind}{将有序数组转化为二叉树}{}
	先找到根节点，如果只有一个数则其就是根节点。如果有2个数需要选择一个作为根节点然后另一个作为子节点，这时候有两种选择，第一种是第一个所在为根第二个作为子节点。第二种则是第二个作为根第一个作为子节点。任选一种方法就可以。对于3个以上的数根节点无疑是中间的元素，接着对其左右的元素分别递归构建树即可。
\end{Mind}
实现\coderef{code:arrayToBST}。
\begin{longlisting}
	\caption{转换数组为二叉树}
	\cppfile[firstline=661,lastline=674]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:arrayToBST}
\end{longlisting}
% \subsection{重建二叉树}
% \begin{example}{重建二叉树}
% 	输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和终须遍历的结果都不包含重复数字。例如，输入前序遍历序列[1,2,4,7,3,5,6,8]和中序遍历列表[4,7,2,1,5,3,8]，则重建如\figref{fig:rebuild_tree}的二叉树并输出它的头节点。
% \end{example}
% \begin{figure}[!htbp]
% 	\centering
% 	\includegraphics[width=0.5\textwidth]{rebuild_tree}
% 	\caption{重建的二叉树}
% 	\label{fig:rebuild_tree}
% \end{figure}

% \begin{Mind}{重建二叉树思路}{}
% 	\figref{fig:tree_array}前序遍历的第一个元素为树的根节点，中序遍历根节点左右分别为子树。
% \end{Mind}
% \begin{figure}[!htbp]
% 	\centering
% 	\includegraphics[width=0.6\textwidth]{tree_array}
% 	\caption{前序和中序遍历序列}
% 	\label{fig:tree_array}
% \end{figure}

\subsection{重建二叉树(前中)}
\begin{example}{通过前序和中序重建二叉树}
	输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和终须遍历的结果都不包含重复数字。例如，输入前序遍历序列[1,2,4,7,3,5,6,8]和中序遍历列表[4,7,2,1,5,3,8]，则重建如\figref{fig:rebuild_tree}的二叉树并输出它的头节点。示意图如\figref{fig:rebuild_tree}。
\end{example}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{rebuild_tree}
	\caption{重建的二叉树}
	\label{fig:rebuild_tree}
\end{figure}

\begin{Mind}{重建二叉树思路}{}
	\figref{fig:tree_array}前序遍历的第一个元素为树的根节点，中序遍历根节点左右分别为子树。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{tree_array}
	\caption{前序和中序遍历序列}
	\label{fig:tree_array}
\end{figure}

\begin{longlisting}
	\caption{重建二叉树}
	\cppfile[firstline=517,lastline=547]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:rebuildBST}
\end{longlisting}
实现上C++无法像python一样优雅的切片，这里实现的时候通过前序索引和中序索引来实现切片。
\subsection{重建二叉树(中后)}
如\figref{fig:rebuild_tree}后续遍历结果为[7,4,2,5,8,6,3,1]。如\figref{fig:buildTreeIP}，根据后续遍历数组的最后一个元素确定根节点，然后根据中序遍历根节点所在位置将其左右划分为子树，递归构造。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{buildTreeIP}
	\caption{重建二叉树（中后）}
	\label{fig:buildTreeIP}
\end{figure}
\begin{longlisting}
	\caption{重建二叉树(IP)}
	\cppfile[firstline=607,lastline=631]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:rebuildIP}
\end{longlisting}
\subsection{二叉树的最小绝对差}
\begin{example}[二叉树的最小绝对差]
	给你一个二叉搜索树的根节点 root ，返回树中任意两不同节点值之间的最小差值。差值是一个正数，其数值等于两值之差的绝对值。
\end{example}
\begin{Mind}{二叉树的最小绝对差}{}
	二叉搜索树的中序遍历为有序数组，最小元素差一定在两个相邻元素之间产生。中序遍历之后再求相邻元素之间的差会导致O(n)的空间复杂度。
\end{Mind}
\begin{Mind}{二叉树的最小绝对差}{}
	记录下当前节点到叶子节点的最小差值。
\end{Mind}
\subsection{二叉搜索树第k大的数}
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{bstKthLargest}
	\caption{二叉搜索树第k大的数}
	\label{fig:bstKthLargest}
\end{figure}
\begin{Mind}{二叉搜索树第k大的数思路}{}
	常规中序遍历获得从小到大的n个数，然后索引num[n-k]或者中序遍历的时候从右节点开始获取从大到小的n个数索引num[k-1]（本实现\coderef{code:bstKthLargest}）。
\end{Mind}

\begin{longlisting}
	\caption{二叉搜索树第k大的数}
	\cppfile[firstline=438,lastline=451]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:bstKthLargest}
\end{longlisting}
\subsection{之字型遍历二叉树}
如\figref{fig:zigzagLevelOrder}第一层从左往右打印，第二层从右往左打印，以此类推。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.4\textwidth]{pos_neg_tree}
	\caption{之字型打印}
	\label{fig:zigzagLevelOrder}
\end{figure}
\begin{Mind}{之字型打印}{}
	如\figref{fig:zhitravel}使用两个栈，奇数偶数栈先放左节点然后放右节点，偶数栈反之。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{zhitravel}
	\caption{之字遍历}
	\label{fig:zhitravel}
\end{figure}
\begin{longlisting}
	\caption{之字遍历}
	\cppfile[firstline=5,lastline=48]{third_party/coding/cxx/algorithm/datastruct/src/zigzagLevelOrder.cc}
	\label{code:zigzagTraver}
\end{longlisting}

\subsection{是否为平衡二叉树}
平衡二叉树\textcolor{red}{每个节点}是指二叉树的左右子树的高度差$\leq 1$。
\begin{Mind}{平衡二叉树}{}
	对根节点判断左右子树高度差是否$<=1$，如果是则对其左右子节点分别递归判断。直到碰到叶子节点（左右子节点为空），返回 true 。
\end{Mind}
\begin{longlisting}
	\caption{是否为平衡二叉树}
	\cppfile[firstline=683,lastline=689]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:isBalanced}
\end{longlisting}
\subsection{在树中寻找和为指定值的路径打印出来}
\begin{example}[在树中寻找和为指定值的路径]
	\begin{figure}[H]
		\centering
		\includegraphics[width=0.5\textwidth]{find_path}
		\caption{和为指定值的路径}
		\label{fig:find_path}
	\end{figure}
	如\figref{fig:find_path}树中和为22的路径有10-5-7和10-12。输出结果如下：
	\begin{Textcode}
		10 5 7
		10 12
	\end{Textcode}
\end{example}
\begin{Mind}{算法思路}{}
	如果节点不为空，取出节点的值，然后看其左右子树是不是叶子节点。如果是的话以左右子树作为当前节点递归调用。当到达叶子节点同时和不为指定值说明叶子节点不合适，删除叶子节点的值。否则当到达叶子节点并且和为指定值的时候输出路径。
\end{Mind}
\begin{longlisting}
	\caption{二叉树的路径}
	\cppfile[firstline=6,lastline=24]{third_party/coding/cxx/algorithm/datastruct/src/pathSum.cc}
	\label{code:bstPathSum}
\end{longlisting}
\subsection{二叉树展开为链表}
\begin{example}
	\figref{fig:flatten}给你二叉树的根结点 root ，请你将它展开为一个单链表：
\begin{itemize}
	\item 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
	\item 展开后的单链表应该与二叉树先序遍历顺序相同。
\end{itemize}
\end{example}
\begin{figure}
	\centering
	\includegraphics[width=\textwidth]{flatten}
	\caption{二叉树转换为链表}
	\label{fig:flatten}
\end{figure}
实现\coderef{code:flatten}
\begin{longlisting}
	\caption{二叉树转换为链表}
	\cppfile[firstline=410,lastline=427]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:flatten}
\end{longlisting}

\subsection{二叉搜索树的最近公共祖先}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.4\textwidth]{commonParent}
	\caption{二叉树的公共祖先}
	\label{fig:commonParent}
\end{figure}
\begin{definition}[二叉搜索树的公共祖先]
	最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）
\end{definition}

\textbf{二叉搜索树}决定了使用$log(N)$可以遍历到树中的节点。
\begin{Mind}{二次遍历法}{}
首先可以确定节点是树中的节点，自然可以容易的找到该节点，同时记录根节点到其的路径。通过两次遍历获取到达目标节点p和q的路径。然后从根节点开始遍历直到找到最后一个公共节点，该节点就是其公共祖先。
\end{Mind}
\begin{itemize}
	\item 时间复杂度：$O(n)$（最坏情况下为链表，需要遍历整棵树找到路径）。
	\item 空间复杂度：$O(n)$（最坏的情况需要存储整颗树）。
\end{itemize}

\begin{Mind}{递归遍历法}{}
	假设f(x)表示以x为根节点的子树包含p或者q。如果是则结果为True，否则为False。最后的节点$x_i$一定满足两个条件：
\begin{enumerate}
	\item $f(x_{il}) and f(x_{ir})$（$x_i$的左右子树均包含p或者q）
	\item $(x_i=p||x_i = q) and (f(x_{il})||f(x_{ir}))$当前节点已经是p或者q的时候只需要左右子树包含另一个节点。
\end{enumerate}
\end{Mind}
以\figref{fig:commonParent}作为例子，hasChild函数递归走到节点4的时候，它的左右节点3，5均不满足包含节点4。于是退栈到4，此时包含节点4，则此时以其为节点的是否包含p或者q的值为True。继续退栈到2，此时结果依然是True。退栈到6，这时候左边分支递归结束，递归调用右分支。此时同理找到9的时候结果为True，退栈到8结果也为True，退栈到6。此时6这个节点同时满足了左右均包含p或者q。此时6为目标节点。
递归遍历法实现如\coderef{code:commonParentOfTree}。C++实现中有个小技巧：我们在满足条件的时候获取节点，通过外部传入指针的引用来实现保存满足条件的节点同时函数能返回正常bool的结果。而递归函数返回的结果和实际节点条件是不一样的。判断是否包含应该是当前节点的左节点或者右节点的结果代表的就是包含p或者q的结果。而包含p或者q还有可能是和p或者q的值相同。而筛选节点则要求递归遍历法中的条件满足。
\begin{longlisting}
	\caption{二叉搜索树的公共祖先}
	\cppfile[firstline=156,lastline=174]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:commonParentOfTree}
\end{longlisting}
\subsection{二叉搜索树迭代器}
\begin{example}
实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
\begin{itemize}
	\item BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
	\item boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
	\item int next()将指针向右移动，然后返回指针处的数字。
\end{itemize}
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
\end{example}
\begin{longlisting}
	\caption{中序遍历迭代器}
	\cudafile[firstline=2,lastline=18]{third_party/coding/cxx/algorithm/datastruct/src/BSTIterator.cc}
	\label{code:bstIterator}
\end{longlisting}

% \subsection{是否为完全二叉树}
% 给定一个二叉树，确定他是否是一个完全二叉树。完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）

\subsection{二叉树的最大路径和}
\begin{example}
	二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径至少包含一个节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其最大路径和 。例如\figref{fig:maxPathSum}最优路径为15->20->7结果为42。
\end{example}
\begin{Mind}{二叉树的最大路径和}{}
	递归计算左右根节点和左节点，根节点和右节点，左右根三者之和记录最大路径和。值得注意的是单节点也可以作为路径，这意味着如果以左右节点计算路径和小于0，那根节点就不用带上左右节点。
\end{Mind}
\begin{figure}
	\centering
	\includegraphics[width=0.5\textwidth]{maxPathSum}
	\caption{二叉树的最大路径和}
	\label{fig:maxPathSum}
\end{figure}
路径是指一个节点能走到另一个节点，这条线路中所有的节点组成一条路径，一个节点也是一条路径。如\figref{fig:maxPathSum}，以20-15-7三个节点为例，他们可以组成20-15这个路线，也可以组成20-7这条路线，也可以组成20-15-7这条路线，我们选择这条因为和最大（42）。在节点-10视角下，它和左边的9组合为-1，右边的20组合结果为32，此时最大路径都小于42。因此最大路径为42。事实上我们可以发现：\textbf{最大路径和可能经过根节点也可能不经过，原则就是选择路线中哪个更大}。所以我们递归的计算:
\begin{enumerate}
	\item	\begin{itemize}
	        \item 根节点和左边最大路径和（不选择右分支）
	        \item 根节点和右边最大路径和（不选择左分支）
	        \item 根节点和左右一起的路径和（左右分支都选择）
		\end{itemize}
	\item 如果左右节点的最大路径和<0的时候，事实上不经过左右节点，直接用根节点能获得更大的和。
\end{enumerate}
\coderef{code:maxPathSum}实现中是否选择左右分支可以通过分支和与0比较，假设l是左分支的计算和，max(0,l)表达式最小都为0，这意味着如果l<0则这个分支被抛弃，结果为0。递归计算的三种情况可以简单地写成max(0,l)+max(0,r)+root->val。分支计算的时候返回应该是左右分支中值更大的分支，但是这个分支结果可能<0，这样就出现第四种情况，这是只要根节点的值即可。C++中递归函数实现返回两个参数，一个是return的结果，一个是记录下的最大值val。值得注意的是通过传入引用记录最大值这种操作在一些语言中可能无法生效。比如python中基础变量是传值。这种写法不适用于Python，python可以通过捕获值实现相同的操作。
\begin{longlisting}
	\caption{二叉树的最大路径和}
	\cppfile[firstline=498,lastline=515]{third_party/coding/cxx/algorithm/datastruct/src/TreeAlgorithm.cc}
	\label{code:maxPathSum}
\end{longlisting}
\section{优先队列}
\subsection{合并n组有序数组}
\begin{example}[合并n个有序数组]
	合并n个有序数组，同时去除重复元素。例如[[1,3,5],[2,4],[0,7,8,1]]合并之后的结果为[0,1,2,3,4,5,7,8]。
\end{example}
\begin{Mind}{合并有序数组同时去除重复元素}{}
	首先将每组数组的第一个元素，数组索引，元素索引放入最小堆(优先队列)。然后将堆顶元素取出，获取到最小值。因为记录了最小值所在数组和元素索引。我们知道下次加入堆的元素是此数组对应索引的下一个元素。将对应的数组编号和下一个元素索引以及对应的元素加入堆，如此反复即可获取所有的最小值。因为需要去重，元素加入结果数组的时候的时候需要保证其比数组中最后一个元素更大。
\end{Mind}
\subsection{查找和最小的 K 对数字}
\begin{example}[查找和最小的 K 对数字]
给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。请找到和最小的 k 个数对 ($u_1$,$v_1$),  ($u_2$,$v_2$)  $\ldots$  ($u_k$,$v_k$) 。输入: nums1 = [1,2,4,5,6], nums2 = [3,5,7,9], k = 3。

输出: [1,3],[2,3],[1,5]
\end{example}
\begin{Mind}{查找和最小的k对数字}{}
	两个数组中分别取第一个元素得到的和肯定是最小的。然后将后选项此小项加入队列，找出次小元素中的最小元素作为次小结果加入目标。如此反复直到找到k个为止。
\end{Mind}
优先队列可以保证加入的元素和是最小的。但是不能简单地交错加入。可能会重复，如\figref{fig:kSmallestPairsRepeat}比如位置(0,1)它可以加入(0,2)和(1,1)而位置(1,0)可以加入(2,0)和(1,1)。这样（1,1）就被加入了两次。
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.4\textwidth]{kSmallestPairsRepeat}
	\caption{选择下一个元素可能导致重复加入}
	\label{fig:kSmallestPairsRepeat}
\end{figure}
为了避免重复加入，我们采用\figref{fig:kSmallestPairsRepeatSet}中的规则加入：
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{kSmallestPairsRepeatSet}
	\caption{改编加入规则去重}
	\label{fig:kSmallestPairsRepeatSet}
\end{figure}
算法实现\coderef{code:kSmallestPairs}
\begin{longlisting}
	\caption{查找和最小的k对数字}
	\cppfile[firstline=36,lastline=71]{third_party/coding/cxx/algorithm/datastruct/src/datastruct_common.cc}
	\label{code:kSmallestPairs}
\end{longlisting}
\subsection{\href{https://leetcode.cn/problems/find-median-from-data-stream/description/?envType=study-plan-v2&envId=top-interview-150}{数据流的中位数}}
\begin{example}[数据流的中位数]
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。

void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：
\begin{Textcode}
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
\end{Textcode}
\end{example}
\begin{Mind}{数据流的中位数}{}
	使用两个优先队列smaller（最大堆）和larger作为成员变量（最小堆），保证smaller中的元素个数$smaller.size() - larger.size()\leq1$。初始化两个堆没有元素的情况下，将元素加入smaller。然后下一个元素如果比当前元素大则放入larger。因为保证smaller最多比larger多一个元素，奇数元素下则smaller比larger多一个元素，其值为中位数。
\end{Mind}
\figref{fig:MedianFinder}中，初始情况-1加入smaller。接下来看-2比中位数更小（此时smaller堆顶的元素就是中位数），同样放到smaller。smaller不满足比larger最多多一个元素的情况。将smaller中更大的元素弹出加入larger。接着-3加入smaller，-4加入smaller同样不满足比larger多一个元素，将此时栈顶的元素加入larger。
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{MedianFinder}
	\caption{数据流中的中位数}
	\label{fig:MedianFinder}
\end{figure}
\begin{longlisting}
	\caption{数据流中的中位数}
	\cudafile[firstline=6,lastline=36]{third_party/coding/cxx/algorithm/datastruct/include/MedianFinder.h}
	\label{code:MedianFinder}
\end{longlisting}

\section{栈}
\subsection{简化路径}
\begin{example}[简化路径]
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为 更加简洁的规范路径。在 Unix 风格的文件系统中规则如下：
\begin{itemize}
	\item 一个点 '.' 表示当前目录本身。两个点 '..' 表示将目录切换到上一级（指向父目录）。
	\item 任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
	\item 任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。
	\item 始终以斜杠 '/' 开头。
	\item 两个目录名之间必须只有一个斜杠 '/' 。
	\item 最后一个目录名（如果存在）不能 以 '/' 结尾。
	\item 路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
\end{itemize}
返回简化后得到的 规范路径 。
\end{example}
\begin{Mind}{简化路径}{}
对于目录中条目，如果为.则可以不用管，如果是..意味着需要删除条目。这样遍历/分割的条目。如果条目为.或者为空则直接跳过。如果为..则将加入的元素最后元素退出。否则将条目加入。最终用加入的条目得到最终的路径。
\end{Mind}
C++实现中根据字符串获取条目的函数需要自己实现，同时根据条目合成字符串的函数也许要实现。实现起来看起来更复杂一些，但是算法本身不复杂。
\subsection{逆波兰表达式求值}
\begin{example}[逆波兰表达式求值]
给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
\end{example}
注意：
\begin{itemize}
	\item 有效的算符为 '+'、'-'、'*' 和 '/' 。
	\item 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
	\item 两个整数之间的除法总是 向零截断 。
	\item 表达式中不含除零运算。
	\item 输入是一个根据逆波兰表示法表示的算术表达式。
	\item 答案及所有中间计算结果可以用 32 位 整数表示。
\end{itemize}
\begin{Mind}{逆波兰表达式求值}{}
遍历tokens，如果是数据则数据入数据栈，如果是操作则将数据栈中元素弹出参与运算之后压栈。然后继续按照同样地办法直到最后完成整个运算。
\end{Mind}
\begin{longlisting}
	\caption{逆波兰表达式求值}
	\cudafile[firstline=74,lastline=98]{third_party/coding/cxx/algorithm/datastruct/src/datastruct_common.cc}
	\label{code:rpn}
\end{longlisting}
\subsection{最长有效括号}
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
\begin{Textcode}
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
\end{Textcode}
\begin{Mind}{最长有效括号}{}
	\begin{itemize}
		\item 对于遇到的每个‘(’ ，我们将它的下标放入栈中。
		\item 对于遇到的每个‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：
		      \begin{itemize}
			      \item 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」。
			      \item 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」。
		      \end{itemize}
	\end{itemize}
\end{Mind}
\begin{longlisting}
	\caption{最长有效括号}
	\cudafile[firstline=4,lastline=21]{third_party/coding/cxx/algorithm/datastruct/src/longestValidParentheses.cc}
	\label{code:longestValidParentheses}
\end{longlisting}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{longestValidParentheses}
	\caption{输入"())((())"计算示意图}
	\label{fig:longestValidParentheses}
\end{figure}
需要注意的是如果记录()分别是0和1有效括号数是1-0+1=2。为了省去这个+1操作，我们可以对栈中元素先出栈然后计算和栈顶元素的差。所以我们最开始初始化栈的时候设置初始值为-1。
\subsection{基本计算器}
\begin{example}[基本计算器]
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
\end{example}
\begin{Mind}{基本计算器}{}
	算法核心在于如果-(a + b)这样的操作如果发现了-，计算括号中的结果的时候其中的符号都要取反。加入策略：
	\begin{itemize}
		\item 如果是(则将当前符号入栈否则出栈容易导致空栈。
		\item 如果是)则()中的表达式计算完了，需要弹出栈中的符号(-()这种情况说明表达式里面的元素都取了负数，-不再影响之后的计算，弹出它)。
		\item + 则符号为正，并入栈。
		\item 设置符号为-。
	\end{itemize}
\end{Mind}
这里面有几种不同的情况：
\begin{enumerate}
	\item 纯数字：这意味着纯数字字符串的时候我们需要直接转换为数值。
\end{enumerate}
\begin{longlisting}
	\caption{基本计算器}
	\cudafile[firstline=3,lastline=36]{third_party/coding/cxx/algorithm/common/src/calculate.cc}
	\label{code:calculate}
\end{longlisting}
\subsection{下一个更大的元素I}
\begin{example}[下一个更大的元素I]
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

示例 1：
\begin{bash}
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
\end{bash}
\end{example}
\subsection{每日气温}
\begin{example}[每日温度]
请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
\end{example}
\begin{Mind}{每日气温（单调栈）}{}
使用单调栈，单调栈中从栈底到栈顶的元素对应的值依次减小，如果当前出现元素大于栈顶元素，直接入栈当前元素所在索引则破坏了这种规则，所以将栈中元素依次出栈，直到当前元素对应的索引小于栈顶元素时将此元素索引加入。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics*[width=0.6\textwidth]{single_stack}
	\caption{单调栈}
	\label{fig:single_stack}
\end{figure}
入栈顺序：
\begin{enumerate}
	\item 初始状态下栈为空，将0（73的索引）直接入栈。
	\item 当前元素为74（大于栈顶元素所指的值73）。将索引差值1（1-0=1）加入索引0指向的位置（result[0]=1），弹栈，当前元素所在索引1入栈。
	\item 当前元素为75（大于栈顶元素所指值74）。将索引差值1（2-1=1）加入索引1指向位置（result[1]=1），弹栈，当前元素2入栈。
	\item 当前元素71（小于栈顶元素指向值75），索引入栈。
	\item 当前元素69（小于栈顶元素71），索引入栈。
	\item 当前元素72（大于栈顶元素69），将索引差值（5-4=1）指向result[4]=1，弹栈，因为当前元素同时也大于当前栈顶元素，将差值（5-3=2）指向result[3]=2继续弹栈。之后此索引5入栈。
	\item 当前元素76（大于栈顶元素72），将索引差值（6-5=1）指向result[5]=1，弹栈，因为当前元素同时大于当前栈顶元素（75），将差值（6-2=4）指向result[2]=4继续弹栈，之后索引6入栈。
	\item 当前元素73（小于栈顶元素76），当前元素入栈。
\end{enumerate}
\begin{longlisting}
	\caption{每日气温}
	\cppfile[firstline=6,lastline=27]{third_party/coding/cxx/algorithm/common/src/dailyTemperatures.cc}
	\label{code:dailyTemperatures}
\end{longlisting}
\subsection{\href{https://leetcode.cn/problems/sum-of-subarray-minimums/description/?envType=problem-list-v2&envId=monotonic-stack}{子数组的最小值之和}}
\begin{example}[子数组的最小值之和]
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。由于答案可能很大，因此 返回答案模 $10^9 + 7$ 。

示例 1：
\begin{bash}
输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
\end{bash}
\end{example}
\begin{Mind}{子数组的最小值之和}{}
对子数组分成两类：
\begin{enumerate}
	\item 当前元素在最右边，且当前元素最小。
	\item 当前元素在最左边，且当前元素最小。
\end{enumerate}
因为当前元素最小，只需要知道上面两种case总共有多少种情况即可。
\end{Mind}
举个例子：1作为当前元素最右边元素的情况有[3,1]，[3,1,\textcolor{red}{2}]，[3,1,\textcolor{red}{2,4}]这三种情况最小值都是1。然后以1作为最左边元素的情况有：[1],[1,2],[1,2,4]。也就是说以1作为最小值有3+3=中情况。对于情况以我们可以进一步分析，其本质上等于以1左右最右边元素的情况下索引能走到的最大位置。
\begin{table}[!htbp]
	\caption{[3,1,2,4]下最小值}
    \label{tab:minSubarraySum}
    \begin{center}
        \begin{tabular}{m{.2\linewidth}m{.4\linewidth}m{.4\linewidth}}
        \toprule
		当前最小值&当前最小值在右边能到的最大索引&当前最小值在左边能到的最大索引\\
        \midrule
		3&1&1\\
		1&2&3\\
		2&2&1\\
		4&1&1\\
        \bottomrule
        \end{tabular}
    \end{center}
\end{table}
我们来计算以1作为左边元素的最大索引位置。通过单调栈维护单调递减的栈。将1所在的索引加入栈，接着2比栈顶元素大，则意味着加入当前元素不影响最小值，于是更新2是作为左边最小值索引为2，接着4也是同理，这样以1作为左边值的最大索引left[1]为3。如果我们以3作为最左边索引，则先将其索引0加入栈，接着发现1比栈顶元素小（意味着加入元素影响了最小值），于是弹出栈中大于当前元素的索引，将当前索引加入。此时left[0]=1，接着轮到2，2比栈顶
\tabref{tab:minSubarraySum} 中计算实际索引位置所以为数组索引+1.
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{minSubarraySum}
	\caption{计算元素在最右边情况下最小值为索引的元素个数}
	\label{fig:minSubarraySum}
\end{figure}
\figref{fig:minSubarraySum}展示了以元素作为最右边元素，且其值最小的数组个数。以元素为左边元素类似。
\begin{longlisting}
	\caption{子数组的最小值之和}
	\cppfile[firstline=4,lastline=29]{third_party/coding/cxx/algorithm/datastruct/src/sumSubarrayMins.cc}
	\label{code:sumSubarrayMins}
\end{longlisting}

\subsection{判断栈的出栈序列}
\begin{example}[判断出栈序列]
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

输出：true
解释：我们可以按以下顺序执行：

push(1), push(2), push(3), push(4), pop() -> 4,

push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

\end{example}
\begin{Mind}{验证栈序列}{}
	创建一个辅助栈，如果栈为空则将pushed的元素加入。此时就不为空了，然后将pushed的元素一个个入栈，直到栈顶元素和pushed的当前元素相等。弹出栈顶元素同时push的元素右移动。直到栈最后为空则返回true否则返回false。算法示意图如：\figref{fig:validateStackSequences}。
\end{Mind}
\begin{figure}[H]
	\centering
	\includesvg[width=.6\textwidth]{validateStackSequences}
	\caption{验证栈序列}
	\label{fig:validateStackSequences}
\end{figure}
代码实现\coderef{code:validateStackSequences}。
\begin{longlisting}
	\caption{验证栈序列}
	\cudafile[firstline=116,lastline=135]{third_party/coding/cxx/algorithm/datastruct/src/datastruct_common.cc}
	\label{code:validateStackSequences}
\end{longlisting}

\subsection{接雨水}
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
\begin{Textcode}
	输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
	输出：6
	解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（绿色部分表示雨水）。
\end{Textcode}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.95\textwidth]{trap}
	\caption{接雨水}
	\label{fig:trap}
\end{figure}
示例如\figref{fig:trap}。
\begin{Mind}{接雨水（暴力解法）}{}
	对于每个柱子找到左右最大高的柱子，然后装水由两边柱子中比较矮的柱子决定。给这个柱子带来的装水量就是min(leftHeight,rightHeight)-height[i]，遍历所有柱子求和即可。
\end{Mind}
暴力解法时间复杂度$O(n^2)$，这里展示是为了引出单调栈算法如何解决这个问题。下面使用单调减栈记录最小最大元素。算法如下：
\begin{Mind}{接雨水（单调减栈）}{}
\begin{enumerate}
	\item 遍历height，如果栈中元素为0则直接入栈。
	\item 如果下一个元素$\leq$栈顶元素则直接入栈，否则弹出栈顶元素，弹出之后的栈顶的元素肯定是大于等于当前弹出栈元素的，height的当前元素是大于出栈元素，可装雨水为两者值较小的那个和当前元素的差乘以i-top-1。更新完装雨水后入栈。
	\item 一直如此遍历直到结束。
\end{enumerate}
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.5\textwidth]{trapStack}
	\caption{单调栈示例}
	\label{fig:trapStack}
\end{figure}
\begin{enumerate}
	\item 索引0入栈。
	\item $height[1]>height[top]$则0出栈，1入栈。
	\item $height[2]\leq height[top]$(top表示单调栈栈顶索引)，2入栈。
	\item $height[3]>height[top]$，索引2出栈，此时对应于\figref{fig:trap}中索引1（栈顶），2（弹出的元素），3（当前）的情况。更新结果为0+(3-1-1)*1=1。此时栈顶元素1依然小于3，出栈，3入栈。
	\item $height[4]\leq height[top]$，4入栈。
	\item $height[5]\leq height[top]$，5入栈。
	\item $height[6]>height[top]$，5出栈，此时当前索引为5，左右大于其的索引为4、6，添加雨水量为min(height[4],height[6])-height[5]。更新结果为res = 1+(6-4-1)*1=2。6入栈。
	\item $height[7]>height[top]$，6出栈，left为4，计算添加雨水高度min(height[4],height[7])-height[6]=0，继续出栈，此时栈为空，无法继续出栈，更新res = 2+(7-3-1)*1=5。
	\item $height[7]>height[top]$（此时top为4）。left=3，添加雨水量为min(height[7],height[3])-height[4]=1更新res = 2+3=5。7入栈。
	\item 同理8，9入栈。
	\item $height[10]>height[top]$，9出栈，left=8，更新结果res=5+1=6，10入栈、11入栈。
\end{enumerate}
暴力解法中我们已经知道，我们需要知道每个索引下左右高于其的高度这样才能更新其高度，暴力解法的过程中需要双指针左右移动导致了$O(n^2)$的时间复杂度，单调栈通过从打大小的更新栈保证了一旦碰到大于栈顶元素的时候就知道了栈顶元素右边大于其的值，通过将其出栈也能得到其左边大于其的值。此时就可以更新结果了。
\begin{longlisting}
	\caption{接雨水（单调栈实现）}
	\cppfile[firstline=30,lastline=48]{third_party/coding/cxx/algorithm/datastruct/src/trap.cc}
	\label{code:trap}
\end{longlisting}
\subsection{去除字符串中重复字母}
\begin{Textcode}
	给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

	示例 1：
	输入：s = "bcabc"
	输出："abc"
	示例 2：
	输入：s = "cbacdcbc"
	输出："acdb"
\end{Textcode}
\subsection{\href{https://leetcode.cn/problems/next-greater-element-ii/submissions/629116398/}{下一个更大元素 II}}
\begin{example}[下一个更大元素 II]
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
 

示例 1:
\begin{bash}
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
\end{bash}
\begin{Mind}{下一个更大元素(单调栈)}{}
这个算法要求循环数组，因此在访问到最后一个元素的时候它可能还需要和第一个元素比。所以我们遍历的时候遍历2*n-1次，这样就不会出现遍历最末尾的元素之后无法和栈最前面的元素比较了。只有元素严格<栈顶元素才出栈。
\end{Mind}
\begin{longlisting}
	\caption{单调栈寻找更大元素}
	\cppfile[firstline=3,lastline=15]{third_party/coding/cxx/algorithm/datastruct/src/nextGreaterElements.cc}
	\label{code:nextGreaterElements}
\end{longlisting}
\subsection{移除重复字符保证最小字典序}
\end{example}
\begin{definition}[字典序]
	字典序最小要求字符串中的每个字符都能尽量保证小的字符在前面。比如"abc"和"ac"相比第二个字符b在c的前面，所以abc的字典序更小。
\end{definition}
\begin{Mind}{思路}{}
	对于字符串中的每个字符，如果有逆序就尝试找到非逆序的字符替换以保证最小字典序。例如示例2：
	\begin{enumerate}
		\item 取出c，放入容器。容器包含c。
		\item 取出b，这时候看到容器里面的c在字符串后面还有，那么直接将b放入则得到cb，但是因为后面还有c，所以将c删除后加入b后续一定能找到bc，容器包含b。
		\item 取出a，同样的道理，后续还有b，则一定能找到ab，这时候删除容器中的元素将a放入。容器包含a。
		\item 取出c，c大于a，合理放入容器，容器包含ac。
		\item 取出d，这时候d大于c，直接放入容器。容器包含acd。
		\item 取出c，c小于d已经存在了，跳到下一个。容器包含acd。
		\item 取出b，b 小于d，b进入容器，容器包含acdb。
		\item 取出c，c大于b，但是c已经存在于容器中了，跳过。容器包含acdb。
	\end{enumerate}
\end{Mind}
因为需要保证遍历的字符比栈中的元素都大（前提是栈中元素在后面用还能找到），这里自然使用单调栈完成。通过字符串模拟单调栈，字符在后面是否存在通过字符串所在索引是否比当前索引大（大说明后面有和栈顶元素相同的元素）。已经入栈的元素通过维护一个in\_stack快速获取字符是否存在于单调栈中。
\begin{longlisting}
	\caption{移除重复字符保证最小字典序}
	\cppfile{third_party/coding/cxx/algorithm/common/src/removeDuplicateLetters.cc}
	\label{code:removeDuplicateLetters}
\end{longlisting}
\subsection{\href{https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string-ii/description/}{删除字符串中的所有相邻重复项 II}}
\begin{example}[删除字符串中的所有相邻重复项 II]
给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。在执行完所有删除操作后，返回最终得到的字符串。

示例 1：

输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。

示例 2：

输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释： 
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"
\end{example}
\begin{Mind}{删除字符串中的所有相邻重复项 II}{}
使用一个栈记录当前字符的索引和出现的次数。给定索引r，r一直右移：
\begin{itemize}
	\item 如果下一个元素（通过索引确定）和当前元素相同则当前元素索引+1，(\textbf{同时更新栈顶索引位置})如果次数=k则删除对应的字符同时将元素出栈。
	\item 如果下一个元素和当前元素不同则当前元素索引和最初初始化次数1加入栈。
\end{itemize}
\end{Mind}
\begin{figure}
	\centering
	\includesvg[width=\textwidth]{removeDuplicates2}
	\caption{删除字符串中所有相邻重复项II示意图}
	\label{fig:removeDuplicates2}
\end{figure}
以deeedbbcccbdaa为例，如\figref{fig:removeDuplicates2}，因为字符串长度>1，所以直接初始化栈st = [0,1]=['d',1]
\begin{enumerate}
	\item 索引为0，下一个字符为e，和当前字符d不像等，则(1,1)入栈。
	\item e的下一个索引为2，字符和当前字符e相等，将栈顶元素的次数+1，如此更新直到索引为3，删除e。此时s为ddbbcccbdaa。
	\item 此时栈顶记录的(0,1)记录了上一个不满足被删除条件的位置，然后下一个元素d和当前相同，更新栈顶次数为2。
	\item 同理加入栈顶元素并更新[2,2]。
	\item 更新栈顶元素(4,3)，c次数为2，删除c，此时字符串为ddbbbdaa。
	\item 此时栈顶记录(2,2)，更新r，得到(2,3)出现三个b，删除b。此时字符串为dddaa。
	\item 此时栈顶记录(1,2)，更新r得到(1,3)，删除d元素，此时字符串s=aa。
	\item 此时栈空了，但是r还没有移动到字符串末尾，则(0,1)入栈，直到结束。
\end{enumerate}
\begin{longlisting}
	\caption{删除字符串中的所有相邻重复项 II}
	\cudafile[firstline=158,lastline=189]{third_party/coding/cxx/algorithm/datastruct/src/datastruct_common.cc}
	\label{code:removeDuplicates2}
\end{longlisting}
\coderef{code:removeDuplicates2} 中 179 行计算r的时候需要保证r最少为0，否则0-1导致溢出导致结果错误。
\emph{主要注意的是：C++中不同类型的值比较的时候会有隐式转换，例如int的-1比size\_t的1要大。编译器对于此类问题可以提供警告：-Wsign-compare。}

上述代码通过反复清除重复元素导致字符串长度时常发生变化，有些语言字符串是不能修改的，为了更通用的算法实现，这里提供了另一个算法：
\begin{Mind}{删除字符串中的所有相邻重复项 II（思路2）}{}
在\coderef{code:removeDuplicates2}中因为原位删除需要知道索引，栈中保存的是索引。现在我们不原位删除字符串，所以不用记录索引。我们只需要使用同样地规则记录字符和字符出现的次数，一旦次数达到k，则出栈。否则栈顶元素对应的次数+1。
\end{Mind}
\begin{longlisting}
	\caption{删除字符串中的所有相邻重复项 II（不删除）}
	\cudafile[firstline=191,lastline=216]{third_party/coding/cxx/algorithm/datastruct/src/datastruct_common.cc}
	\label{code:removeDuplicates3}
\end{longlisting}
\coderef{code:removeDuplicates3}中只记录次数不为k的字符和其出现的次数，然后最终通过这个信息组合输出。

